package real.bytedance.dfs_bfs;

import java.util.*;

import org.junit.Test;

//检测几个序列是否存在循环依赖，如[A, B][B, C][C, A]，存在依赖A -> B -> C -> A
/* 
    使用拓扑排序，若能成功则没有依赖，否则存在依赖
*/
public class CycleDependency {

    /* 
        1.建立节点与出度节点的映射
        2.建立节点与被依赖次数的映射
    */
    public boolean hasCycleDependency(char[][] seqs) {
        int len = seqs.length, idx, count = 0, d;
        int[] nums = new int[26];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            idx = seqs[i][0] - 'A';
            nums[idx]++;
            count++;
            d = seqs[i][1] - 'A';
            if (map.containsKey(d)) {
                map.get(d).add(idx);
            } else {
                List<Integer> list = new LinkedList<>();
                list.add(idx);
                map.put(d, list);
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            if (nums[(idx = seqs[i][1] - 'A')] == 0) { //在被依赖的节点中寻找0入度节点
                queue.offer(idx);
            }
        }
        if (count > 0 && queue.size() == 0) return true; //根本没有0入度的节点，存在循环依赖
        while (!queue.isEmpty()) {
            idx = queue.poll(); //拿出一个0入度节点，对其出度节点进行遍历，依次入度减一
            nums[idx] = -1; //标记为访问过
            count--; //总计依赖次数减一
            if (count == 0) return false;

            //又忘记了，当只剩下最后一个节点时，确实是导致空指针异常的
            List<Integer> list = map.get(idx);
            if (list.isEmpty()) continue;
            for (int i = 0; i < list.size(); i++) {
                int cur = list.get(i);
                nums[cur]--;
                if (nums[cur] == 0) queue.offer(cur); //若因为依赖消失，而入度为0，加入0入度队列
            }
        }
        return count > 0; //还存在节点有依赖，且找不到0入度节点入队，证明有循环依赖
    }

    @Test
    public void test() {
        char[][] seqs = {{'A','B'}, {'B', 'C'}, {'C', 'D'}, {'D', 'B'}};
        System.out.println(hasCycleDependency(seqs));
    }
}


/* 

            idx = seqs[i][0] - 'A'; //记录这个字符依赖他人的数量
            nums[idx]++; //该字符的依赖次数加一
            count++; //总依赖次数，用于判断拓扑排序是否成功
            d = seqs[i][1] - 'A';
            if (map.containsKey(idx)) {
                List<Integer> list = map.get(idx);
                list.add(seqs[i][0] - 'A');
                map.put(idx, list);
            } else {
                List<Integer> list = new LinkedList<>();
                list.add(seqs[i][0] - 'A');
                map.put(idx, list);
            }
*/